import java.util.HashSet;

public class RemoveReation {
    public static void main1(String[] args) {
        int[]data={1,6,5,6,8,5,9};
        Node head = new Node(0); //设置为哑元
        Node p =head;
        for(int i=0;i<data.length;i++){
            p.next=new Node(data[i]);
            p=p.next;
        }
        Node p1 = head.next;
        remove(p1);
        Node p2=head.next;
        while(p2!=null){
            System.out.print(p2.value+" ");
            p2=p2.next;
        }
    }

    public static void main(String[] args) {
        int[]data={1,3,8,2,7};
        Node head = new Node(0); //哑元单元
        Node p =head;
        for(int i=0;i<data.length;i++){
            p.next=new Node(data[i]);
            p=p.next;
        }
        Node p1 = head.next;
        Node ac= fun(p1,6);
        System.out.println("111");


    }
    public static Node fun(Node head,int x){
        if(head==null){
            return null;
        }
        Node as=null;
        Node ae=as;
        Node bs=null;
        Node be=bs;
        while(head!=null){
            if(head.value<x){
                if(as==null){
                    as=new Node(head.value);
                    ae=as;

                }else{
                    ae.next=new Node(head.value);
                    ae=ae.next;
                }
            }else{
                if(bs==null){
                    bs=new Node(head.value);
                    be=bs;

                }else{
                    be.next=new Node(head.value);
                    be=be.next;
                }
            }
            head=head.next;
        }
        ae.next=bs;
        return as;

    }
    private static void remove(Node head) {

        HashSet<Object> hashSet = new HashSet<>();

        Node prev=head;
        while(head!=null){
            if(hashSet.contains(head.value)){
                prev.next=head.next;
            }else{
                hashSet.add(head.value);
                prev=head;
            }
            head=head.next;
        }
    }

    private static class Node{

        public Node next;
        public  int value;
        public Node(int value){
            this.value=value;
        }
    }



        public Node partition(Node pHead, int x) {

            // write code herepublic class Partition {



            if(pHead==null){

                return null;

            }

           Node bs=null;

           Node be=bs;

         Node as=null;

          Node ae=as;

            while(pHead!=null){

                if(pHead.value<x){

                    if(bs==null){

                        bs=pHead;

                        be=pHead;

                    }else{

                        be.next=pHead;

                        be=be.next;

                    }

                    pHead=pHead.next;

                }else{

                    if(as==null){

                        as=pHead;

                        ae=pHead;

                    }else{

                        ae.next=pHead;

                        ae=ae.next;;

                    }

                    pHead=pHead.next;

                }

            }

            if(bs==null){//bs

                return as;

            }

            be.next=as;

            if(as==null){

                return bs;

            }

            be.next=as;

            ae.next=null;

            return bs;

        }

    }
